package com.example.sort;

import java.util.HashMap;
import java.util.Map;

/**
 * 排序的各种实现
 */
public class SortSolution {

    /**
     * 冒泡排序
     *
     * @param numbers
     */
    public static void sort(int[] numbers) {
        for (int i = 0; i < numbers.length - 1; i++) {
            for (int j = 0; j < numbers.length - 1 - i; j++) {
                if (numbers[j] > numbers[j + 1]) {
                    int temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 快速排序
     * 1). 先从数列中取出一个数作为基准数。
     * 2). 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
     * 3). 再对左右区间重复第二步，直到各区间只有一个数。
     */
    public static void quickSort(int[] arr, int low, int high) {
        int left, right, temp, t;
        if (low > high) {
            return;
        }
        left = low;
        right = high;
        temp = arr[low];
        while (left < right) {
            while (temp <= arr[right] && left < right) {
                right--;
            }
            while (temp >= arr[left] && left < right) {
                left++;
            }
            if (left < right) {
                t = arr[right];
                arr[right] = arr[left];
                arr[left] = t;
            }
        }
        arr[low] = arr[left];
        arr[right] = temp;
        quickSort(arr, low, right - 1);
        quickSort(arr, right + 1, high);
    }

    /**
     * 选择排序
     *
     * @param arr
     */
    public static void selectSort(int[] arr) {
//        int[] arr = new int[]{5, 3, 6, 2, 10, 2, 1};
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (i != minIndex) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
        }
    }

    /**
     * 插入排序
     */
    public static void insertSort(int[] arrs) {

    }

    /**
     * 堆排序
     */
    public static void heapSort(int[] arr, int start, int end) {
        int current = start;
        int left = 2 * current + 1;
        int temp = arr[current];

        for (; left <= end; current = left, left = 2 * left + 1) {
            if (left < end && arr[left] < arr[left + 1]) {
                left++;
            }
            if (temp >= arr[left]) {
                break;
            } else {
                arr[current] = arr[left];
                arr[left] = temp;
            }
        }


    }





    /**
     * 数字反转  比如:123->321
     *
     * @param x
     * @return
     */
    public static int reverse(int x) {
        int result = 0;
        while (x != 0) {
            int i = x % 10;
            x = x / 10;
            if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && i > 7)) {
                return 0;
            }
            if (result < Integer.MIN_VALUE / 10 || (result == Integer.MIN_VALUE / 10 && i < -8)) {
                return 0;
            }
            result = result * 10 + i;
        }
        return result;
    }


    /**
     * String str = "(()())";
     *
     * @param s
     * @return
     */
    public static int getRes(String s) {
        if (s == null || s.length() < 2) return 0;
        int pre = 0;
        int res = 0;
        int[] dp = new int[s.length()];
        char[] arr = s.toCharArray();
        for (int i = 1; i < s.length(); i++) {
            if (arr[i] == ')') {
                pre = i - dp[i - 1] - 1;
                if (pre >= 0 && arr[pre] == '(') {
                    //注意这里得加括号  艹...
                    dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
                    res = Math.max(res, dp[i]);
                }
            }
        }
        return res;
    }


    public static int lengthOfLongestSubString(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0;
        for (int j = 0; j < s.length(); j++) {
            int i = dic.getOrDefault(s.charAt(j), -1);
            dic.put(s.charAt(j), j);
            tmp = tmp < j - 1 ? tmp + 1 : j - 1;
            res = Math.max(res, tmp);
        }
        return res;
    }

    public static Map<String, String> find(String str) {
        int count, max = 0;
        String substr = null;
        String temp = null;
        for (int i = str.length(); i >= 1; i--) {
            for (int j = 0; j < str.length() - i + 1; j++) {
                count = 0;
                substr = str.substring(j, i);
                for (int k = 0; k < str.length() - i + 1; i++) {
                    if (!substr.equals(str.substring(k, i))) {
                        count++;
                    }

                }
                if (count > max) {
                    max = count;
                    temp = substr;
                }
            }
        }
        Map<String, String> map = new HashMap<>();
        map.put(temp, String.valueOf(max));
        return map;
    }

    public static void print(int[][] nums) {
        int rows = nums.length;
        int columns = nums[0].length;
        int left = 0;
        int right = columns - 1;
        int top = 0;
        int bottom = rows - 1;
        while (left <= right && top <= bottom) {
            for (int t = left; t <= right; t++) {
                System.out.println(nums[top][t]);
            }
            for (int t = top + 1; t <= bottom; t++) {
                System.out.println(nums[t][right]);
            }
            if (top != bottom) {
                for (int t = right - 1; t >= left; t--) {
                    System.out.println(nums[bottom][t]);
                }
            }
            if (left != right) {
                for (int t = bottom - 1; t >= top; t--) {
                    System.out.println(nums[t][left]);
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
    }


    public static void main(String[] args) throws ClassNotFoundException {
        int[] numbers = new int[]{1, 5, 8, 2, 3, 9, 4};
//        sort(numbers);
//        print(numbers);

        int[] arr = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
//        quickSort(arr, 0, arr.length - 1);
//        print(arr);

        String str = "abcbcbcabc";
//        Map<String, String> map = find(str);
//        map.forEach((k, v) -> {
//            System.out.println("key->" + k + ", value->" + v);
//        });
//        System.out.println(lengthOfLongestSubString(str));

//        int n = numbers.length;
//        int i;
//        for (i = n / 2 - 1; i >= 0; i--) {
//            heapSort(numbers, i, n - 1);
//        }
//        int k = 2;
//        for (i = n - 1; i >= k - 1; i--) {
//            exchange(numbers[0], numbers[i]);
//            heapSort(numbers, 0, i - 1);
//        }
//        System.out.println(1);

        int[][] mn = new int[3][4];
        mn[0] = new int[]{1, 2, 3, 4};
        mn[1] = new int[]{5, 6, 7, 8};
        mn[2] = new int[]{9, 10, 11, 12};
        print(mn);

    }

    public static void print(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            System.out.println(nums[i]);
        }
    }

    public static void exchange(int a, int b) {
        int tmp = a;
        a = b;
        b = tmp;
    }
}
